{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# 二十一点 Blackjack-v0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/zzx/.local/lib/python3.10/site-packages/ale_py/roms/utils.py:90: DeprecationWarning: SelectableGroups dict interface is deprecated. Use select.\n",
      "  for external in metadata.entry_points().get(self.group, []):\n"
     ]
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "import numpy as np\n",
    "np.random.seed(0)\n",
    "import matplotlib.pyplot as plt\n",
    "import gym"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### 环境使用"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "ename": "DeprecatedEnv",
     "evalue": "Env Blackjack-v0 not found (valid versions include ['Blackjack-v1'])",
     "output_type": "error",
     "traceback": [
      "\u001B[0;31m---------------------------------------------------------------------------\u001B[0m",
      "\u001B[0;31mKeyError\u001B[0m                                  Traceback (most recent call last)",
      "File \u001B[0;32m~/.local/lib/python3.10/site-packages/gym/envs/registration.py:158\u001B[0m, in \u001B[0;36mEnvRegistry.spec\u001B[0;34m(self, path)\u001B[0m\n\u001B[1;32m    157\u001B[0m \u001B[38;5;28;01mtry\u001B[39;00m:\n\u001B[0;32m--> 158\u001B[0m     \u001B[38;5;28;01mreturn\u001B[39;00m \u001B[38;5;28;43mself\u001B[39;49m\u001B[38;5;241;43m.\u001B[39;49m\u001B[43menv_specs\u001B[49m\u001B[43m[\u001B[49m\u001B[38;5;28;43mid\u001B[39;49m\u001B[43m]\u001B[49m\n\u001B[1;32m    159\u001B[0m \u001B[38;5;28;01mexcept\u001B[39;00m \u001B[38;5;167;01mKeyError\u001B[39;00m:\n\u001B[1;32m    160\u001B[0m     \u001B[38;5;66;03m# Parse the env name and check to see if it matches the non-version\u001B[39;00m\n\u001B[1;32m    161\u001B[0m     \u001B[38;5;66;03m# part of a valid env (could also check the exact number here)\u001B[39;00m\n",
      "\u001B[0;31mKeyError\u001B[0m: 'Blackjack-v0'",
      "\nDuring handling of the above exception, another exception occurred:\n",
      "\u001B[0;31mDeprecatedEnv\u001B[0m                             Traceback (most recent call last)",
      "Input \u001B[0;32mIn [3]\u001B[0m, in \u001B[0;36m<module>\u001B[0;34m\u001B[0m\n\u001B[0;32m----> 1\u001B[0m env \u001B[38;5;241m=\u001B[39m \u001B[43mgym\u001B[49m\u001B[38;5;241;43m.\u001B[39;49m\u001B[43mmake\u001B[49m\u001B[43m(\u001B[49m\u001B[38;5;124;43m\"\u001B[39;49m\u001B[38;5;124;43mBlackjack-v0\u001B[39;49m\u001B[38;5;124;43m\"\u001B[39;49m\u001B[43m)\u001B[49m\n\u001B[1;32m      2\u001B[0m env\u001B[38;5;241m.\u001B[39mseed(\u001B[38;5;241m0\u001B[39m)\n\u001B[1;32m      3\u001B[0m \u001B[38;5;28mprint\u001B[39m(\u001B[38;5;124m'\u001B[39m\u001B[38;5;124m观察空间 = \u001B[39m\u001B[38;5;132;01m{}\u001B[39;00m\u001B[38;5;124m'\u001B[39m\u001B[38;5;241m.\u001B[39mformat(env\u001B[38;5;241m.\u001B[39mobservation_space))\n",
      "File \u001B[0;32m~/.local/lib/python3.10/site-packages/gym/envs/registration.py:235\u001B[0m, in \u001B[0;36mmake\u001B[0;34m(id, **kwargs)\u001B[0m\n\u001B[1;32m    234\u001B[0m \u001B[38;5;28;01mdef\u001B[39;00m \u001B[38;5;21mmake\u001B[39m(\u001B[38;5;28mid\u001B[39m, \u001B[38;5;241m*\u001B[39m\u001B[38;5;241m*\u001B[39mkwargs):\n\u001B[0;32m--> 235\u001B[0m     \u001B[38;5;28;01mreturn\u001B[39;00m \u001B[43mregistry\u001B[49m\u001B[38;5;241;43m.\u001B[39;49m\u001B[43mmake\u001B[49m\u001B[43m(\u001B[49m\u001B[38;5;28;43mid\u001B[39;49m\u001B[43m,\u001B[49m\u001B[43m \u001B[49m\u001B[38;5;241;43m*\u001B[39;49m\u001B[38;5;241;43m*\u001B[39;49m\u001B[43mkwargs\u001B[49m\u001B[43m)\u001B[49m\n",
      "File \u001B[0;32m~/.local/lib/python3.10/site-packages/gym/envs/registration.py:128\u001B[0m, in \u001B[0;36mEnvRegistry.make\u001B[0;34m(self, path, **kwargs)\u001B[0m\n\u001B[1;32m    126\u001B[0m \u001B[38;5;28;01melse\u001B[39;00m:\n\u001B[1;32m    127\u001B[0m     logger\u001B[38;5;241m.\u001B[39minfo(\u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mMaking new env: \u001B[39m\u001B[38;5;132;01m%s\u001B[39;00m\u001B[38;5;124m\"\u001B[39m, path)\n\u001B[0;32m--> 128\u001B[0m spec \u001B[38;5;241m=\u001B[39m \u001B[38;5;28;43mself\u001B[39;49m\u001B[38;5;241;43m.\u001B[39;49m\u001B[43mspec\u001B[49m\u001B[43m(\u001B[49m\u001B[43mpath\u001B[49m\u001B[43m)\u001B[49m\n\u001B[1;32m    129\u001B[0m env \u001B[38;5;241m=\u001B[39m spec\u001B[38;5;241m.\u001B[39mmake(\u001B[38;5;241m*\u001B[39m\u001B[38;5;241m*\u001B[39mkwargs)\n\u001B[1;32m    130\u001B[0m \u001B[38;5;28;01mreturn\u001B[39;00m env\n",
      "File \u001B[0;32m~/.local/lib/python3.10/site-packages/gym/envs/registration.py:185\u001B[0m, in \u001B[0;36mEnvRegistry.spec\u001B[0;34m(self, path)\u001B[0m\n\u001B[1;32m    176\u001B[0m toytext_envs \u001B[38;5;241m=\u001B[39m [\n\u001B[1;32m    177\u001B[0m     \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mKellyCoinflip\u001B[39m\u001B[38;5;124m\"\u001B[39m,\n\u001B[1;32m    178\u001B[0m     \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mKellyCoinflipGeneralized\u001B[39m\u001B[38;5;124m\"\u001B[39m,\n\u001B[0;32m   (...)\u001B[0m\n\u001B[1;32m    182\u001B[0m     \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mHotterColder\u001B[39m\u001B[38;5;124m\"\u001B[39m,\n\u001B[1;32m    183\u001B[0m ]\n\u001B[1;32m    184\u001B[0m \u001B[38;5;28;01mif\u001B[39;00m matching_envs:\n\u001B[0;32m--> 185\u001B[0m     \u001B[38;5;28;01mraise\u001B[39;00m error\u001B[38;5;241m.\u001B[39mDeprecatedEnv(\n\u001B[1;32m    186\u001B[0m         \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mEnv \u001B[39m\u001B[38;5;132;01m{}\u001B[39;00m\u001B[38;5;124m not found (valid versions include \u001B[39m\u001B[38;5;132;01m{}\u001B[39;00m\u001B[38;5;124m)\u001B[39m\u001B[38;5;124m\"\u001B[39m\u001B[38;5;241m.\u001B[39mformat(\n\u001B[1;32m    187\u001B[0m             \u001B[38;5;28mid\u001B[39m, matching_envs\n\u001B[1;32m    188\u001B[0m         )\n\u001B[1;32m    189\u001B[0m     )\n\u001B[1;32m    190\u001B[0m \u001B[38;5;28;01melif\u001B[39;00m env_name \u001B[38;5;129;01min\u001B[39;00m algorithmic_envs:\n\u001B[1;32m    191\u001B[0m     \u001B[38;5;28;01mraise\u001B[39;00m error\u001B[38;5;241m.\u001B[39mUnregisteredEnv(\n\u001B[1;32m    192\u001B[0m         \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mAlgorithmic environment \u001B[39m\u001B[38;5;132;01m{}\u001B[39;00m\u001B[38;5;124m has been moved out of Gym. Install it via `pip install gym-algorithmic` and add `import gym_algorithmic` before using it.\u001B[39m\u001B[38;5;124m\"\u001B[39m\u001B[38;5;241m.\u001B[39mformat(\n\u001B[1;32m    193\u001B[0m             \u001B[38;5;28mid\u001B[39m\n\u001B[1;32m    194\u001B[0m         )\n\u001B[1;32m    195\u001B[0m     )\n",
      "\u001B[0;31mDeprecatedEnv\u001B[0m: Env Blackjack-v0 not found (valid versions include ['Blackjack-v1'])"
     ]
    }
   ],
   "source": [
    "env = gym.make(\"Blackjack-v0\")\n",
    "env.seed(0)\n",
    "print('观察空间 = {}'.format(env.observation_space))\n",
    "print('动作空间 = {}'.format(env.action_space))\n",
    "print('动作数量 = {}'.format(env.action_space.n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### 同策回合更新\n",
    "回合更新预测"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "def ob2state(observation):\n",
    "    return observation[0], observation[1], int(observation[2])\n",
    "\n",
    "def evaluate_action_monte_carlo(env, policy, episode_num=500000):\n",
    "    q = np.zeros_like(policy)\n",
    "    c = np.zeros_like(policy)\n",
    "    for _ in range(episode_num):\n",
    "        # 玩一回合\n",
    "        state_actions = []\n",
    "        observation = env.reset()\n",
    "        while True:\n",
    "            state = ob2state(observation)\n",
    "            action = np.random.choice(env.action_space.n, p=policy[state])\n",
    "            state_actions.append((state, action))\n",
    "            observation, reward, done, _ = env.step(action)\n",
    "            if done:\n",
    "                break # 回合结束\n",
    "        g = reward # 回报\n",
    "        for state, action in state_actions:\n",
    "            c[state][action] += 1.\n",
    "            q[state][action] += (g - q[state][action]) / c[state][action]\n",
    "    return q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "policy = np.zeros((22, 11, 2, 2))\n",
    "policy[20:, :, :, 0] = 1 # >= 20 时收手\n",
    "policy[:20, :, :, 1] = 1 # < 20 时继续\n",
    "\n",
    "q = evaluate_action_monte_carlo(env, policy) # 动作价值\n",
    "v = (q * policy).sum(axis=-1) # 状态价值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "def plot(data):\n",
    "    fig, axes = plt.subplots(1, 2, figsize=(9, 4))\n",
    "    titles = ['without ace', 'with ace']\n",
    "    have_aces = [0, 1]\n",
    "    extent = [12, 22, 1, 11]\n",
    "    for title, have_ace, axis in zip(titles, have_aces, axes):\n",
    "        dat = data[extent[0]:extent[1], extent[2]:extent[3], have_ace].T\n",
    "        axis.imshow(dat, extent=extent, origin='lower')\n",
    "        axis.set_xlabel('player sum')\n",
    "        axis.set_ylabel('dealer showing')\n",
    "        axis.set_title(title)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "def play_once(env):\n",
    "    total_reward = 0\n",
    "    observation = env.reset()\n",
    "    print('观测 = {}'.format(observation))\n",
    "    while True:\n",
    "        print('玩家 = {}, 庄家 = {}'.format(env.player, env.dealer))\n",
    "        action = np.random.choice(env.action_space.n)\n",
    "        print('动作 = {}'.format(action))\n",
    "        observation, reward, done, _ = env.step(action)\n",
    "        print('观测 = {}, 奖励 = {}, 结束指示 = {}'.format(\n",
    "                observation, reward, done))\n",
    "        total_reward += reward\n",
    "        if done:\n",
    "            return total_reward # 回合结束\n",
    "\n",
    "print(\"随机策略 奖励：{}\".format(play_once(env)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot(v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "带起始探索的回合更新"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def monte_carlo_with_exploring_start(env, episode_num=500000):\n",
    "    policy = np.zeros((22, 11, 2, 2))\n",
    "    policy[:, :, :, 1] = 1.\n",
    "    q = np.zeros_like(policy)\n",
    "    c = np.zeros_like(policy)\n",
    "    for _ in range(episode_num):\n",
    "        # 随机选择起始状态和起始动作\n",
    "        state = (np.random.randint(12, 22),\n",
    "                 np.random.randint(1, 11),\n",
    "                 np.random.randint(2))\n",
    "        action = np.random.randint(2)\n",
    "        # 玩一回合\n",
    "        env.reset()\n",
    "        if state[2]: # 有A\n",
    "            env.player = [1, state[0] - 11]\n",
    "        else: # 没有A\n",
    "            if state[0] == 21:\n",
    "                env.player = [10, 9, 2]\n",
    "            else:\n",
    "                env.player = [10, state[0] - 10]\n",
    "        env.dealer[0] = state[1]\n",
    "        state_actions = []\n",
    "        while True:\n",
    "            state_actions.append((state, action))\n",
    "            observation, reward, done, _ = env.step(action)\n",
    "            if done:\n",
    "                break # 回合结束\n",
    "            state = ob2state(observation)\n",
    "            action = np.random.choice(env.action_space.n, p=policy[state])\n",
    "        g = reward # 回报\n",
    "        for state, action in state_actions:\n",
    "            c[state][action] += 1.\n",
    "            q[state][action] += (g - q[state][action]) / c[state][action]\n",
    "            a = q[state].argmax()\n",
    "            policy[state] = 0.\n",
    "            policy[state][a] = 1.\n",
    "    return policy, q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "policy, q = monte_carlo_with_exploring_start(env)\n",
    "v = q.max(axis=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot(policy.argmax(-1))\n",
    "plot(v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于柔性策略的回合更新"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def monte_carlo_with_soft(env, episode_num=500000, epsilon=0.1):\n",
    "    policy = np.ones((22, 11, 2, 2)) * 0.5 # 柔性策略\n",
    "    q = np.zeros_like(policy)\n",
    "    c = np.zeros_like(policy)\n",
    "    for _ in range(episode_num):\n",
    "        # 玩一回合\n",
    "        state_actions = []\n",
    "        observation = env.reset()\n",
    "        while True:\n",
    "            state = ob2state(observation)\n",
    "            action = np.random.choice(env.action_space.n, p=policy[state])\n",
    "            state_actions.append((state, action))\n",
    "            observation, reward, done, _ = env.step(action)\n",
    "            if done:\n",
    "                break # 回合结束\n",
    "        g = reward # 回报\n",
    "        for state, action in state_actions:\n",
    "            c[state][action] += 1.\n",
    "            q[state][action] += (g - q[state][action]) / c[state][action]\n",
    "            # 更新策略为柔性策略\n",
    "            a = q[state].argmax()\n",
    "            policy[state] = epsilon / 2.\n",
    "            policy[state][a] += (1. - epsilon)\n",
    "    return policy, q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "policy, q = monte_carlo_with_soft(env)\n",
    "v = q.max(axis=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "plot(policy.argmax(-1))\n",
    "plot(v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 异策回合更新\n",
    "重要性采样策略评估"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate_monte_carlo_importance_sample(env, policy, behavior_policy,\n",
    "        episode_num=500000):\n",
    "    q = np.zeros_like(policy)\n",
    "    c = np.zeros_like(policy)\n",
    "    for _ in range(episode_num):\n",
    "        # 用行为策略玩一回合\n",
    "        state_actions = []\n",
    "        observation = env.reset()\n",
    "        while True:\n",
    "            state = ob2state(observation)\n",
    "            action = np.random.choice(env.action_space.n,\n",
    "                    p=behavior_policy[state])\n",
    "            state_actions.append((state, action))\n",
    "            observation, reward, done, _ = env.step(action)\n",
    "            if done:\n",
    "                break # 玩好了\n",
    "        g = reward # 回报\n",
    "        rho = 1. # 重要性采样比率\n",
    "        for state, action in reversed(state_actions):\n",
    "            c[state][action] += rho\n",
    "            q[state][action] += (rho / c[state][action] * (g - q[state][action]))\n",
    "            rho *= (policy[state][action] / behavior_policy[state][action])\n",
    "            if rho == 0:\n",
    "                break # 提前终止\n",
    "    return q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "policy = np.zeros((22, 11, 2, 2))\n",
    "policy[20:, :, :, 0] = 1 # >= 20 时收手\n",
    "policy[:20, :, :, 1] = 1 # < 20 时继续\n",
    "behavior_policy = np.ones_like(policy) * 0.5\n",
    "q = evaluate_monte_carlo_importance_sample(env, policy, behavior_policy)\n",
    "v = (q * policy).sum(axis=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "plot(v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "重要性采样回合更新"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def monte_carlo_importance_sample(env, episode_num=500000):\n",
    "    policy = np.zeros((22, 11, 2, 2))\n",
    "    policy[:, :, :, 0] = 1.\n",
    "    behavior_policy = np.ones_like(policy) * 0.5 # 柔性策略\n",
    "    q = np.zeros_like(policy)\n",
    "    c = np.zeros_like(policy)\n",
    "    for _ in range(episode_num):\n",
    "        # 用行为策略玩一回合\n",
    "        state_actions = []\n",
    "        observation = env.reset()\n",
    "        while True:\n",
    "            state = ob2state(observation)\n",
    "            action = np.random.choice(env.action_space.n,\n",
    "                    p=behavior_policy[state])\n",
    "            state_actions.append((state, action))\n",
    "            observation, reward, done, _ = env.step(action)\n",
    "            if done:\n",
    "                break # 玩好了\n",
    "        g = reward # 回报\n",
    "        rho = 1. # 重要性采样比率\n",
    "        for state, action in reversed(state_actions):\n",
    "            c[state][action] += rho\n",
    "            q[state][action] += (rho / c[state][action] * (g - q[state][action]))\n",
    "            # 策略改进\n",
    "            a = q[state].argmax()\n",
    "            policy[state] = 0.\n",
    "            policy[state][a] = 1.\n",
    "            if a != action: # 提前终止\n",
    "                break\n",
    "            rho /= behavior_policy[state][action]\n",
    "    return policy, q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "policy, q = monte_carlo_importance_sample(env)\n",
    "v = q.max(axis=-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "plot(policy.argmax(-1))\n",
    "plot(v)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}